在深入探討 Linux Kernel 的網路系統之前，我們可以先來了解一個在 Linux Kernel 中廣泛使用的資料結構：雙向鏈結串列 (Double Linked List)。這種資料結構的使用方式非常有趣，很有C語言這樣能直接操作記憶體的特色，也常見於 Kernel 的設計中。

Double Linked List簡介

Double linked list 是一種非常常用的資料結構，每個節點都包含指向前一個與下一個節點的指標欄位，頭尾節點通常互相指向，因此我們可以藉由遍歷這些指標來遍歷整個 List。

struct Something {
    struct Something *next, *prev;
}

struct ListNode {
    struct ListNode *next, *prev;
    // struct Something *element
    void *element;
}

我們可以想到兩種常見的實現方式：

1. 在每個節點內直接定義兩個指標 next 和 prev，來指向前後的節點。
2. 建立一個 ListNode 結構來保存 next 和 prev 指標，並且使用一個 element 指標來指向實際的節點結構。若是專用的 ListNode，可以直接使用 struct Something* 作為指標，但為了通用性，這裡使用 void 指標，使其能指向任意的資料結構。

Linux Kernel 的通用Double Linked List

在 Linux Kernel 中，採用了通用的List節點結構 list_head。

// include/linux/types.h#L190
struct list_head {
	struct list_head *next, *prev;
};

但當我們看到 list_head，可能會感到困惑，因為它並沒有直接指向具體資料的欄位。Linux Kernel 利用了指標運算與記憶體偏移量，來實現對資料結構的訪問。

struct Something {
    int a;
    int b;
    struct list_head head;
}

// 取得 list 的第一個元素
struct list_head *cursor = get_first_element(); 
struct Something *element = container_of(cursor, struct Something, head); 

// 取得 list 鏈結串列的第二個元素
element = container_of(cursor->next, struct Something, head);

假設我們有一個 Something 結構，希望能使用 Double Linked List 來串聯許多 Something，那麼可以如上所示，在 Something 結構中定義一個名為 head 的欄位，其類型為 struct list_head（注意，這裡不是指標）。

當我們獲得指向 list_head 的指標 cursor 後，可以使用 Linux Kernel 提供的Macro container_of，從cursor指標中取得對應節點的 Something 結構指標。

container_of 的參數有三個：

1. 當前的 cursor 指標變數。
2. 使用這個 List 的結構，在此例中為struct Something
3. list_head在結構Somthing裡面欄位的名稱。

透過這個方式，我們可以取得 Something 結構的指標。同樣地，對 cursor->next 使用 container_of，即可取得 list 的下一個節點。

container_of 的運作

為了理解 container_of 的運作方式，我們需要看看 Something 結構在記憶體中的佈局。假設我們有一個 Something 的實例 oneSomething，其在記憶體中的狀態可能如下圖所示：

假設我們有一個指標 toOne 指向 oneSomething，這個指標會儲存指向 oneSomething 中第一個元素，也就是 a 的記憶體地址 0x00010。

如果我們有一個 list_head 指標 cursor，目的是指向 oneSomething 這個節點，那麼這個指標會指向 oneSomething 中的 head 欄位，其地址為 0x00018。

container_of(cursor, struct Something, head) 的作用就是從 cursor 指標計算出 toOne 指標，也就是從地址 0x00018 計算出地址 0x00010。這相當簡單，因為 cursor - 0x00008 就能得到 toOne，而這個 0x00008 是固定的，因為 struct Something 的記憶體佈局在編譯時已經確定，因此 container_of 可以在編譯時計算出靜態的記憶體偏移量。

所以，container_of MACRO不僅適用於 list_head，也能適用於任何欄位，只要你提供一個內部欄位的指標和變數名稱，就能計算出整個結構的指標。這樣可以省去在設計中額外儲存 element 指標的空間，但使用者需要自行確保 cursor 指向的確實是某個結構中的欄位，否則 container_of 計算出的地址可能無法正確指向有效的資料。

結論

今天我們介紹了 list_head 這個資料結構以及 container_of 的機制，這兩者都是 Linux Kernel 中常用的技術，隨著我們進一步探討 Linux Kernel 的網路系統，這些概念會在後續文章中頻繁出現。